package stackAndQueue.q5_getMaxWindow;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * Project：algorithm
 * Date：2024/6/11
 * Time：19:12
 * Description：一个整形数组arr和一个大小为w的窗口从数组的左边滑到右边，窗口每次移动一个位置。例：数组arr为{4,5,4,3,6,5},窗口大小为3
 *     [4 5 4] 3 6 5    最大值5
 *     4 [5 4 3] 6 5    最大值5
 *     4 5 [4 3 6] 5    最大值6
 *     4 5 4 [3 6 5]    最大值6
 * 如果数组长度为n，窗口大小为w，则会产生n-w+1个窗口最大值
 * 实现一个函数，输入数组arr和窗口大小w，得到长度为n-w+1的窗口最大值数组
 *
 * 解法：双端队列
 * 维护一个双端队列qmax，队列中存放的是窗口最大值的索引。
 * 遍历数组arr，对于每个元素arr[i]，维护qmax队列，队列中存放的是窗口最大值的索引。
 * 首先，将qmax队列中比arr[i]小的元素删除，因为窗口已经滑动，窗口最大值不可能再比arr[i]小。
 * 然后，将arr[i]加入qmax队列，因为窗口已经滑动，窗口最大值可能变成arr[i]。
 * 最后，如果qmax队列的第一个元素等于i-w，说明窗口已经滑动w个位置，窗口最大值已经不在窗口内，需要删除qmax队列的第一个元素。
 * 遍历完成后，qmax队列中存放的就是窗口最大值的索引，将其转换为窗口最大值数组。
 *
 * @author Cao Jiwen
 * @version 1.0
 */
public class GetMaxWindow {

    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || w > arr.length) {
            return null;
        }
        LinkedList<Integer> qmax = new LinkedList<>();
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {
                qmax.pollLast();
            }
            qmax.addLast(i);
            if (qmax.peekFirst() == i - w){
                qmax.pollFirst();
            }
            if (i >= w - 1) {
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
        int w = 3;
        int[] res = getMaxWindow(arr, w);
        System.out.println(Arrays.toString(res));
    }
}
